1. Field of the Invention
The present invention relates to computer displays. More specifically, the present invention relates to a method for the approximation of caps of smooth line segments on computer displays.
2. The Background
A computer display is made up of rows and columns of pixels. Each pixel may be very small. However, computer display technology has not yet advanced to the point where the pixels are small enough to avoid several limitations encountered when graphics are viewed by the human eye.
Sampling of images to be displayed on a computer, or of equations representing lines, results in a somewhat jagged appearance, also called the xe2x80x9cstaircasexe2x80x9d effect. This is due to the fact that the sampling process digitizes coordinate points on an object or line to discrete integer pixel positions, resulting in an image having staggered edges. This distortion is also called xe2x80x9caliasingxe2x80x9d. FIG. 1 is a diagram illustrating the staircase effect. Line 10 is sampled and then displayed using a group of shaded pixels 12. One can see by viewing the shaded pixels 12 that they appear jagged and suffer from the staircase effect.
Techniques used to decrease the aliasing suffered in computer graphics are known collectively as antialiasing techniques. The most obvious antialiasing technique is to simply increase the resolution of the display, so that each pixel is smaller. However, as discussed earlier, computer monitor technology as of yet does not provide for a display with such small pixels that aliasing is not viewable to the human eye.
A common antialiasing method is to increase the sampling rate by treating the display as if it were covered by a finer grid than it really is. This is known as supersampling. Supersampling works best on displays which are capable of displaying pixels at different intensities.
Typical supersampling techniques attempt to smooth the staircase effect by using the surrounding pixels. FIG. 2 is a diagram illustrating a supersampling technique applied to the aliased line of FIG. 1. The group of shaded pixels 50 is now much wider than in FIG. 1, and there is less of a staircase effect simply because they are wider. However, this technique also utilizes the ability to vary intensity of each pixel to smooth the edges of the line. For example, without the ability to vary intensities, pixel 52 would have to be completely shaded. However, by varying the intensity of pixel 52, it gives the viewer the impression that only a region of pixel 52 is filled, and thus makes the line appear much smoother.
One drawback to supersampling is that identifying subpixels to be selectively turned on and off requires a larger number of calculations than simply determining which pixels are along a line path. These calculations are further complicated by the fact that the position of the line path within each pixel Varies depending on the slope of the line. In a 45-degree line, the line path cuts each pixel in half diagonally, but a 30-degree line path does not.
Endpoints of a line, which are referred to in this application as caps, require very complex calculations, such as inverse squares. FIG. 3 is a diagram illustrating a single pixel containing an end-point of a line. The mathematical line 100 is known, and therefore the length of segment c can be determined fairly easily. However, the area of the entire shaded region 102 must be determined in order to determine the intensity of the pixel and the orientation of the subpixels. This involves numerous computations using the Pythagorean theorem, beginning with determining a from b and c (according to the Pythagorean theorem, a2+b2=c2, so in order to determine a, a square root, or in computer terms inverse root must be computed).
An inverse root is one of the most complicated computations a processor can make. In recent years, there has been movement away from powerful mainframe computers to smaller, cheaper, less powerful processors, such as those that may be contained in set-top boxes and hand-held devices.
While in a large computer, antialiasing techniques may be applied using hardware, such as graphics cards, the space is not available for such hardware in these smaller, less powerful processors. Additionally, the cost of implementing the techniques in hardware may be prohibitive. Therefore, it would be preferable to perform such techniques using software.
However, performing the traditional antialiasing in software would take too much processing power due to all the inverse squares that would have to be calculated, which would slow down the processor to intolerable levels. What is needed is a solution which allows for an antialiasing technique to be applied which could be performed by software but which does not use as much processing power as traditional antialiasing techniques.
Starting and ending caps of smooth line segments may be drawn on a computer display without complicated calculations and avoiding the use of inverse square root calculations by drawing the caps using rectangles. The direction of the line segment may be determined, and using the direction certain pixels in a four-pixel grouping may be selectively illuminated. The normalized intensity values of the illuminated pixels may be determined by computing an x-fraction and a y-fraction, representing the distance in the x-direction and y-direction between a sample origin point in a corner of the four-pixel grouping and the closest corner of a region covered by the mathematical origin or endpoint corrected for the thickness of the line segment. It is generally preferable for only two pixels to be illuminated for each cap, the pixels chosen according to a formula ensuring that there are no perception problems when two smooth line segments share a common mathematical origin or endpoint.